from typing import List


class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        n = len(nums)
        st = [] # 单调递减栈
        # 正序遍历，获得一个包含nums[0]的单调数组/单调栈
        for i, x in enumerate(nums):
            # 如果栈为空，或者栈顶大于当前元素，则入栈
            # 性质：
            # 设原栈顶对应的下标为 j
            # 可以注意到，如果入栈，那么nums[j+1:i] >= nums[j]
            if not st or nums[st[-1]] > x:
                st.append(i)
        # 逆序遍历
        # 这里也运用了贪心的思路
        # 因为是逆序遍历，所以如果栈在过程中没有pop
        # 那么后遍历的一定不可能获得比先遍历的更长的区间
        # 也就是说想要获得更优的结果，必须要pop
        ans = 0
        print(st)
        for i in range(n - 1, -1, -1):
            x = nums[i]
            # 如果栈顶元素小于等于，则满足题目要求，出栈并记录结果
            # 直到栈顶元素大于当前元素，这时无法获得更长的区间了
            # 设最后出栈的下标为 r，当前栈顶对应的下标为 l
            # 这个时候nums[l+1:r] >= nums[l]
            # 因此这些元素也不满足要求
            # 但是下一次如果栈顶出栈，这些元素因为大于栈顶
            # 所以不可能获得更长的区间，因此被排除
            while st and nums[st[-1]] <= x:
                j = st.pop()
                # 在pop的同时更新答案，循环内是满足题目要求的情况
                ans = max(ans, i - j)
        return ans
